#include <string>
class Solution {
public:
    vector<string> ret;
    set<string> st;
    int vis[20] = { 0 };
    string path;
    int len;
    void dfs(string& s, int index)
    {
        if (index == len)
        {
            st.insert(path);
            return;
        }

        for (int i = 0; i < len; i++)
        {
            if (vis[i] == 0)
            {
                vis[i] = 1;
                path.push_back(s[i]);
                dfs(s, index + 1);
                path.pop_back();
                vis[i] = 0;
            }
        }
    }

    vector<string> Permutation(string str)
    {
        len = str.size();
        sort(str.begin(), str.end());
        dfs(str, 0);
        for (auto& s : st) ret.push_back(s);
        return ret;
    }
};